package arithmetic.sort;


import static utils.ListNodeUtils.printLink;

import java.util.Arrays;
import java.util.List;
import java.util.concurrent.TimeUnit;

import org.junit.jupiter.api.Test;

import com.google.common.collect.Lists;

import utils.ListNodeUtils.ListNode;


/**
 * @author jiangfeng on 2022/5/31
 */
public class LinkSort {
    //1 任务的队列, ABCD
    //2.相同任务需要延迟执行 A,A,B    -> AB_A
    // 间隔时间2单位

    public static void main2(String[] args) throws InterruptedException {
        int[] arr = {1, 2, 1};
        List<String> list = Lists.newArrayList("A", "B", "A");
        int temp = 2;

        for (int i : arr) {
            //

            TimeUnit.SECONDS.sleep(1);
        }
    }

    // 链表排序
    public static void main(String[] args) {

        int[] linkArray = new int[]{4,19,14,5,-3,1,8,5,11,15};
        //int[] linkArray = new int[]{4,1,2,3};
        //int[] linkArray = new int[]{44,1,2,3,5};

        ListNode listNode1 = genLink(linkArray);

       /*
       数组的插入排序
       int[] a = {3,5,6,1,2,6};
        insertSort(a);
        System.out.println(Arrays.toString(a));
        */


        printLink(listNode1);
        //LinkNode linkNode = linkInsertSort(linkNode1);
        ListNode listNode = sortList2(listNode1);
        printLink(listNode);

    }



    // 链表插入排序
    public static ListNode linkInsertSort(ListNode head) {
        //第一轮循环 找到第一个元素的位置. // 定义一个哑节点
        ListNode preHead = new ListNode(-1);
        preHead.next = head;

        ListNode index = head;
        ListNode preIndex = preHead;
        while (index != null) {
            // 链表稍微变通一下 从后向前不好遍历只能从前向后
            ListNode tempNext = index.next;
            boolean isChanged = false;
            ListNode tempIndex = preHead.next;
            ListNode preTempIndex = preHead;
            while (tempIndex != index && tempIndex.next != null) {
                //   tempIndex,    index
                //  1, 2, 3, 4, 5, 6, 7, 8
                // 1 4 2 3
                // 找到
                if (tempIndex.val >= index.val) {
                    // 找到index 的位置了,放在tempIndex前面, 开始重新接链表.
                    preIndex.next = index.next;
                    preTempIndex.next = index;
                    index.next = tempIndex;
                    isChanged = true;
                    // 变了和没变 preIndex逻辑不一样.
                    break;
                }
                //没找到就继续下一个节点
                preTempIndex = tempIndex;
                tempIndex = tempIndex.next;
            }
            index = tempNext;
            if (!isChanged) {
                preIndex = preIndex.next;
            }

        }
        return preHead.next;
    }

    // 15234
    // 4123
    public static ListNode sortList(ListNode head) {
        ListNode preHead = new ListNode();
        preHead.next=head;

        ListNode index = head;
        ListNode preIndex = preHead;
        while(index!=null){
            ListNode index2 = preHead.next;
            ListNode preIndex2 = preHead;
            boolean change = false;
            while(index2!=index && index2!=null ){
                // 从前向后
                if(index2.val >=index.val){
                    // 找到index所在位置,放在index2的前面
                    preIndex2.next = index;
                    preIndex.next = index.next;
                    index.next = index2;
                    change=true;
                    break;
                }
                preIndex2 = index2;
                index2 = index2.next;
            }

            if(!change){
                preIndex = index;
                index=index.next;
            }else{
                index = preIndex.next;
            }

        }
        return preHead.next;

    }



    /**
     * 能用但是非常慢
     * @param head
     * @return
     */
    public static ListNode sortList2(ListNode head) {
        ListNode preHead = new ListNode();
        preHead.next= head;

        ListNode preIndex = preHead;
        while(preIndex.next!=null){
            ListNode preIndex2 = preHead;
            while (preIndex2.next != preIndex.next && preIndex2.next != null && preIndex2.next.val < preIndex.next.val) {
                preIndex2 = preIndex2.next;
            }
            if (preIndex2.next == preIndex.next) {
                preIndex = preIndex.next;
                continue;
            }
            // 找到index所在位置,放在index2的前面
            ListNode index = preIndex.next;
            ListNode Index2 = preIndex2.next;

            preIndex2.next = index;
            preIndex.next = index.next;
            index.next =Index2;

        }
        return preHead.next;
    }

    /**
     * 插入排序
     */
    public static void insertSort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int index = i;
            while (index >= 1) {
                if (a[index-1] > a[index]) {
                    int temp = a[index];
                    a[index] = a[index-1];
                    a[index-1] = temp;
                }
                System.out.println(Arrays.toString(a));
                index--;
            }
        }
    }

    public static void babort(int[] a) {
        for (int i = 0; i < a.length; i++) {
            for (int j = i + 1; j < a.length; j++) {
                if (a[i] > a[j]) {
                    int temp = a[j];
                    a[j] = a[i];
                    a[i] = temp;
                }
            }
        }
    }

    public static ListNode swap(ListNode beforeA, ListNode a, ListNode b) {
        if (beforeA != null) {
            beforeA.next = b;
        }
        a.next = b.next;
        b.next = a;
        return a;
    }

    public static ListNode genLink(int[] a){
        ListNode head = new ListNode(a[0]);
        ListNode next = head;
        for (int i = 1; i < a.length; i++) {
            next.next =new ListNode(a[i]);
            next = next.next;
        }
        return head;
    }




    /**
     * 递归版 归并排序, 自顶向下
     * 2022-06-02 09:05:29
     */
    @Test
    public void testMergeSort(){
        //int[] linkArray = new int[]{4,19,14,5,-3,1,8,5,11,15};
        int[] linkArray = new int[]{4,2,1,3};

        ListNode listNode1 = genLink(linkArray);
        printLink(listNode1);
        //LinkNode linkNode = linkInsertSort(linkNode1);
        ListNode listNode = mergeSort(listNode1);
        printLink(listNode);
    }

    public ListNode mergeSort(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode fast = head, slow = head, pre = head;
        while (fast != null && fast.next != null && slow != null) {
            fast = fast.next.next;
            pre = slow;
            slow = slow.next;
        }
        // pre是slow的前一个指针,断链
        pre.next = null;
        ListNode head1 = mergeSort(head);
        ListNode head2 = mergeSort(slow);
        return merge(head1, head2);
    }

    public ListNode merge(ListNode l1, ListNode l2){
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode l = new ListNode(),temp = l;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                l.next = l1;
                l1 = l1.next;
            } else {
                l.next = l2;
                l2 = l2.next;
            }
            l = l.next;
        }
        if(l1 !=null){
            l.next =l1;
        }
        if(l2 !=null){
            l.next =l2;
        }
        return temp.next;
    }


    /**
     * 非递归版 归并排序, 自低向上
     * 2022-06-02 09:05:29
     */
    @Test
    public void testMergeSort2(){
        int[] linkArray = new int[]{4,19,14,5,-3,1,8,5,11,15};
        //int[] linkArray = new int[]{4,2,1,3};

        ListNode listNode1 = genLink(linkArray);
        printLink(listNode1);
        //LinkNode linkNode = linkInsertSort(linkNode1);
        ListNode listNode = mergeSort2(listNode1);
        printLink(listNode);
    }

    public ListNode mergeSort2(ListNode head){
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummyHead = new ListNode(head);
        // 计算长度
        int listLength = 0;
        while (head != null) {
            head = head.next;
            listLength++;
        }

        // 步长 从最小1开始排序,   tempLength = tempLength << 1    ===> tempLength <<= 1
        for (int tempLength = 1; tempLength <= listLength; tempLength <<= 1) {
            // 没必要使用两段指针, 可以使用dummy的方式实现preIndex.
            // pre 表示前一段的最后一个连接处.
            ListNode pre = dummyHead, index= dummyHead.next;
            while (index != null) {
                ListNode head1 = index;
                // 切第一段 , 这里i需要从1开始.  如果从零开始会多走一步. 下面就做不了断链操作了.  多留一步  index.next!=null
                for (int i = 1; i < tempLength && index != null && index.next != null; i++) {
                    index = index.next;
                }
                ListNode head2 = index.next;
                index.next = null;

                // 切第二段
                index = head2;
                for (int i = 1; i < tempLength && index != null; i++) {
                    index = index.next;
                }
                // 有可能分成奇数段,这里index已经空了
                ListNode next = null;
                if (index != null) {
                    next = index.next;
                    index.next = null;
                }
                // 合并,并且和前一段 最后一个元素粘起来.
                pre.next = merge(head1, head2);
                // 将pre指针维护到前一段的最后一个位置  所以不是 pre!=null
                while (pre.next!=null) {
                    pre = pre.next;
                }
                index = next;
            }
        }
        return dummyHead.next;

    }


    //**提交到leecode出问题的代码 调试**//
    @Test
    public void testMergeSort3(){
        //int[] linkArray = new int[]{4,19,14,5,-3,1,8,5,11,15};
        int[] linkArray = new int[]{4,2,1,3};

        ListNode listNode1 = genLink(linkArray);
        printLink(listNode1);
        //LinkNode linkNode = linkInsertSort(linkNode1);
        ListNode listNode = sortList3(listNode1);
        printLink(listNode);
    }

    public ListNode sortList3(ListNode head) {
        if(head ==null || head.next == null){
            return head;
        }
        // 先计算长度
        ListNode dummyHead = new ListNode(0,head);
        int length = 0;
        while(head!=null){
            head=head.next;
        }
        for(int step = 1;step<length;step<<=1){
            ListNode pre = dummyHead, curr = dummyHead.next;
            while(curr!=null){
                // 找第一段
                ListNode h1 = curr;
                for(int i = 1;curr!=null && curr.next!=null && i<step; i++){
                    curr =curr.next;
                }
                ListNode h2 = curr.next;
                curr.next =null;

                // 找第二段
                curr = h2;
                for(int i = 1;curr!=null  && i< step; i++){
                    curr =curr.next;
                }
                ListNode next = null;
                if(curr!=null){
                    next = curr.next;
                    curr.next = null;
                }
                pre.next = merge3(h1,h2);
                while(pre.next!=null){
                    pre=pre.next;
                }
                curr = next;
            }

        }
        return dummyHead.next;
    }

    public ListNode merge3 (ListNode h1, ListNode h2){
        if(h1==null){
            return h2;
        }
        if(h2==null){
            return h1;
        }
        ListNode dummyHead = new ListNode(),curr = dummyHead;
        while(h1!=null && h2!=null){
            if(h1.val>h2.val){
                curr.next = h2;
                h2 = h2.next;
            }else{
                curr.next = h1;
                h1 = h1.next;
            }
            curr = curr.next;
        }
        if(h1!=null){
            curr.next = h1;
        }
        if(h2!=null){
            curr.next = h2;
        }
        return dummyHead.next;
    }

}
